"""P12 12.基础提升 并查集、KMP算法"""


def infect(data, x, y, row, col):
    """扩散查找函数"""
    if x < 0 or x >= row or y < 0 or y >= col or data[x][y] != 1:
        return
    data[x][y] = 2
    infect(data, x + 1, y, row, col)
    infect(data, x - 1, y, row, col)
    infect(data, x, y + 1, row, col)
    infect(data, x, y - 1, row, col)


def count_islands(data):
    """查找地图data中岛的数量，时间复杂度：O(row * col)"""
    if not data or not data[0]:
        return 0
    row, col = len(data), len(data[0])
    islands = 0
    for i in range(row):
        for j in range(col):
            if data[i][j] == 1:
                islands += 1
                infect(data, i, j, row, col)


"""
并查集：
注意：用户需要先将所有数据提供出来
提供两个方法，时间复杂度接近为O(1)：
is_same_set(a, b) 判断a、b集合是否相等
union(a, b)       合并a、b集合
"""


class Element:

    def __init__(self, value):
        """自定义的包装映射"""
        self.value = value


class UnionFindSet:
    """并查集"""

    element_map = dict()
    # key：数据值，value：Element对象
    father_map = dict()
    # key：某个Element对象，value：该Element对象的父
    size_map = dict()
    # key：某个集合的代表Element对象，value：该集合的大小

    def __init__(self, data):
        for value in data:
            element = Element(value)
            self.element_map[value] = element
            self.father_map[element] = element
            self.size_map[element] = 1

    def find_head(self, element):
        """查找元素element的最上父元素"""
        path = list()
        while element != self.father_map[element]:
            path.append(element)
            element = self.father_map[element]
        while path:
            self.father_map[path.pop(-1)] = element
        return element

    def is_same_set(self, a, b):
        """判断a、b集合是否相等"""
        if a in self.element_map and b in self.element_map:
            return self.find_head(self.element_map[a]) == \
                   self.find_head(self.element_map[b])
        return False

    def union(self, a, b):
        """合并a、b集合"""
        if a in self.element_map and b in self.element_map:
            a_father = self.find_head(self.element_map[a])
            b_father = self.find_head(self.element_map[b])
            if a_father != b_father:
                a_size = self.size_map[a_father]
                b_size = self.size_map[b_father]
                if a_size >= b_size:
                    big_set, small_set = a_father, b_father
                else:
                    big_set, small_set = b_father, a_father
                self.father_map[small_set] = big_set
                self.size_map[big_set] = a_size + b_size
                self.size_map.pop(small_set)


"""
KMP算法：

KMP算法解决的问题：
字符串str1和str2，str1是否包含str2，如果包含，返回str2在str1中的开始位置。
要求数据复杂度：O(N)

next_list中某个节点值的求法：
在str2某个节点的前子串中，前缀和后缀相等的最大长度（前缀和后缀不能取到整体）
人为规定next_list[0] = -1, next_list[1] = 0

KMP算法的大加速（处理str1）：
当str1[i]不等于str2[j]时，通过next_list[j]算出str2[j]节点的前缀后的节点str2[k]，
重新比较str2[k]与str[i]，当k为0时，str1待比较字符后移一位，比较str[i + 1]与str2[0]

KMP算法的小加速（处理str2）：
在str2中，求j位置的next_list值的判断条件：
如果str2[j-1]的值等于next_list[j-1]前缀后一个字符str2[k]，
next_list[j] = next_list[j-1] + 1
如果不同，将str2[k]当作str2[j-1]重新判断，直到k为0
如果k为0，next_list[j] = 0
"""


def get_next_list(data: str) -> list:
    if len(data) == 1:
        return [-1]
    next_list = [-1, 0]
    i, compare = 2, 0
    # compare表示i的前一个字符的前缀子串后的一个字符位置信息，即：next_list[i-1]
    while i < len(data):
        if data[i - 1] == data[compare]:
            compare += 1  # 当前的结果变成下次的前缀值
            next_list.append(compare)
            i += 1
        elif compare > 0:
            compare = next_list[compare]
        else:
            next_list.append(0)
            i += 1
    return next_list


def get_index(str1: str, str2: str) -> int:
    """获取str2在str1中的开始位置"""
    if not str1 or not str2 or len(str1) < len(str2):
        return -1
    i1 = i2 = 0
    next_list = get_next_list(str2)
    while i1 < len(str1) and i2 < len(str2):
        if str1[i1] == str2[i2]:
            i1 += 1
            i2 += 1
        elif next_list[i2] == -1:  # str2的比对位置无法前移了
            i1 += 1
        else:
            i2 = next_list[i2]
    return i1 - i2 if i2 == len(str2) else -1
